ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group97b.txt/000020_icon-group-sender _Thu Jul 10 11:37:00 1997.msg

Internet Message Format | 2000-09-20 | 2KB

Received: from kingfisher.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Thu, 10 Jul 1997 11:16:32 MST
Received: by kingfisher.CS.Arizona.EDU; (5.65v3.2/1.1.8.2/08Nov94-0446PM)
    id AA26576; Thu, 10 Jul 1997 11:16:32 -0700
Message-Id: <[e-mail]>
Date: Thu, 10 Jul 1997 11:37:00 +0300
From: Steven Gross <[e-mail]>
X-Mailer: Mozilla 3.0 (Win95; I)
Mime-Version: 1.0
To: Icon Group <[e-mail]>
Subject: Re: A small puzzle longest common prefix string
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Errors-To: [e-mail]
Status: RO

Three lcp routines.  Each is at least five times faster than the
preceeding one, at least for for very long strings.

procedure lcp1(s1,s2)
# simplest.  char by char match.  easy to generalize for more strings.
    local i
    i := 1
    while s1[i] == s2[i] do i +:= 1
    return s1[1+:i-1]
end

procedure lcp2(s1,s2)
# uses internal string scanning.  doubles chunk scanned each time.
    local i, j
    i := 1;  j := 0;
    while match(s1[j+1 +:i], s2, j+1) do { j+:= i;  i *:= 2 }
    #  or:  while s2 ? (move(j) & =s1[j+1 +: i]) do { j +:= i;  i *:= 2
}
    while j +:= 1 & s1[j] == s2[j]     # check chars from j+1 to i
    return s1[1+:j-1]
end

procedure lcp3(s1,s2)
# uses internal screen scanning, recursion to reuse doubling
   return s1[1+:lcph(s1, s2, 0)]
end

procedure lcph(s1, s2 ,k)
# on entry, s1[1+:k] == s2[1+:k].
#  returns the number of additional chars that match.
    local i, j
    i := 1;  j := 0;
    while match(s1[k+j+1 +:i], s2, k+j+1) do { j +:= i;  i *:= 2 }
    if j=0 then return 0 else return j + lcph(s1, s2, k + j)
end